package listnode;

public class _725_分隔链表 {


    /**
     * 给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
     *
     * 每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
     *
     * 这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
     *
     * 返回一个符合上述规则的链表的列表。
     *
     * 举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param root
     * @param k
     * @return
     */
    public ListNode[] splitListToParts(ListNode root, int k) {
        int len = 0;
        ListNode cur = root;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        int c = len / k;
        int r = len % k;

        ListNode[] result = new ListNode[k];
        cur = root;
        for (int i = 0; i < k; i++) {
            ListNode head = cur;
            for (int j = 0; j < c + (i<r?1:0)-1; j++) {
                if(cur!=null) {
                    cur = cur.next;
                }
            }
            if (cur!=null) {
                ListNode pre = cur;
                cur = cur.next;
                pre.next = null;
            }
            result[i] = head;
        }
        return result;
    }
}
